package com.sicheng.蓝桥.练习题.dp;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/3/23 15:33
 */
public class 包子凑数 {
    /**
     * 小明几乎每天早晨都会在一家包子铺吃早餐。
     * 他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 Ai 个包子。
     * 每种蒸笼都有非常多笼，可以认为是无限笼。
     * 每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。
     * 比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。
     * 当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
     * 当然有时包子大叔无论如何也凑不出顾客想买的数量。
     * 比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。
     * 而顾客想买 7 个包子时，大叔就凑不出来了。
     * 小明想知道一共有多少种数目是包子大叔凑不出来的。
     *
     * 输入格式
     * 第一行包含一个整数 N。
     * 接下来 N 行，每行包含一个整数 Ai。
     *
     * 输出格式
     * 输出一个整数代表答案。
     * 如果凑不出的数目有无限多个，输出INF。
     *
     * 数据范围
     * 1≤N≤100,
     * 1≤Ai≤100
     *
     * 输入样例1：
     * 2
     * 4
     * 5
     *
     * 输出样例1：
     * 6
     *
     * 输入样例2：
     * 2
     * 4
     * 6
     *
     * 输出样例2：
     * INF
     * 样例解释
     * 对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
     * 对于样例2，所有奇数都凑不出来，所以有无限多个。
     * 原文链接：https://blog.csdn.net/weixin_47701814/article/details/114422005
     */

    /**
     * 当俩个数互质，校验到a*b
     * 当不互质有无穷种凑不出来
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int k = 1;
        int countOdd = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            if (nums[i] == 1) {
                System.out.println(0);
                return;
            }
            if (nums[i] % 2 == 1) {
                countOdd++;
            }
            k *= nums[i];
        }

        //没有奇数
        if (countOdd == 0) {
            System.out.println("INF");
            return;
        }
        //todo check 所有num 是否俩俩互质
        //todo if true 有限个凑不出
        //todo if false inf个凑不出
        boolean[] dp = new boolean[(int) 1e6];
        int count = 0;//能凑出的
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] = dp[i - num];
                }
                if (dp[i]) {
                    count++;
                    break;
                }
            }
        }
        //博一博飞机变摩托
        //要是凑不出来的占比超过60%,就认为有无穷多种
        int couldNot = dp.length - 1 - count;
        if (couldNot * 1.0 / (dp.length - 1) > 0.6)
            System.out.println("INF");
        else
            System.out.println(couldNot);

    }

    private static boolean check(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (gcd(nums[i], nums[j]) != 1)
                    return false;
            }
        }
        return true;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

}
